// Copyright (c) 2010, Google Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// ---
// Author: Jeffrey Junfeng Pan (panjunfeng@gmail.com)

#ifndef FP_GROWTH_BASE_H_
#define FP_GROWTH_BASE_H_

#include <cmath>
#include <unordered_map>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

#include "common/logging.h"
#include "common/scoped_ptr.h"

using namespace std;

namespace frequent_pattern_mining {

template <typename T>
struct ItemFrequencyPair {
  T value;        // item value
  int frequency;  // item frequency
};

template <typename T>
struct ItemsetFrequencyPairBase {
  // fields for frequent pattern mining (general purpose).
  vector<T> itemset;      // multiple items form an itemset

  int frequency;          // itemset frequency
};

template <typename T>
struct ItemsetFrequencyPair : public ItemsetFrequencyPairBase<T> {
  // pattern selection for max coverage of transactions.
  // (this is not a part of standard frequent pattern mining algorithm)
  bool is_partial;          // if this itemset is a subset of a parent itemset,
                            // both having the same frequency.

  bool is_phrase;           // if all descendant itemsets have the same
                            // frequency as this one. note that, the definition
                            // of phrase here is different: we do not consider
                            // item order at all.

  int index;                // itemset index. value is set automatically.

  vector<int> parents;      // all the parent indices of this itemset. Itemset B
                            // is said to be a direct parent of Itemset A if
                            // A is a subset of B and B has only one more item
                            // than A. An itemset can have 0, 1 or multiple
                            // parents.

  vector<int> children;     // all the children indices of this itemset.
                            // Itemset B is a child of A if A is B's parent.
};

// An association rule is described as:
//   1) lhs -> rhs
//   2) support: the frequency of the union of lhs and rhs.
//   3) confidence: when lhs happens, the probability that rhs also happens.
template <typename T>
struct AssociationRule {
  ItemsetFrequencyPairBase<T> lhs;  // left hand side of the rule.
  ItemsetFrequencyPairBase<T> rhs;  // right hand side of the rule.
  int combined_frequency;
};

// Count and Ratio Conversion for Frequent Pattern Mining
// Input:  num_transactions >= 0
//         ratio in [0.0, 1.0]
// Return: count in [0, num_transactions]
// Note:   count = ceil(ratio * num_transactions)
inline int GetCountFromRatio(int num_transactions, double ratio) {
  CHECK_GE(num_transactions, 0) << ": number of transactions must be >= 0";
  CHECK_GE(ratio, 0.0) << ": ratio must be >= 0.0";
  LOG_IF(WARNING, ratio > 1.0) << ": ratio <= 1.0";
  return static_cast<int>(ceil(ratio * num_transactions));
}

// Minimal Support Conversion for Frequent Pattern Mining
// Input:  num_transactions >= 0
//         count in [0, num_transactions]
// Return: ratio in [0.0, 1.0]
// Note:   count = ceil(ratio * num_transactions)
inline double GetRatioFromCount(int num_transactions,
                                int count) {
  CHECK_GE(num_transactions, 0) << ": number of transactions must be >= 0";
  CHECK_GE(count, 0) << ": count must be >= 0";
  LOG_IF(WARNING, count > num_transactions) << ": cout <= num_transactions";
  return num_transactions == 0 ? 0 :
    static_cast<double>(count) / static_cast<double>(num_transactions);
}

// convert a string item into string. This overloaded function is necessary
// since we want to convert int/string type data into string. Ideally, we
// need a function that can convert any data type into string.
inline string ItemToString(const string& input) {
  return input;
}

// convert an int item into string
inline string ItemToString(int input) {
  std::stringstream text;
  text << input;
  return text.str();
}

// convert a string to a string item. This overloaded function is necessary
// since we want to convert string type data into int/string item. Similar
// function interface for string/int item.
inline void ItemFromString(const string& input, string* item) {
  *item = input;
}

// convert a string to an int item
inline void ItemFromString(const string& input, int* item) {
  *item = atoi(input.c_str());
}
}  // namespace frequent_pattern_mining

#endif  // FP_GROWTH_BASE_H_
